﻿// Quick_Sort.cpp : Defines the entry point for the application.
// 快速排序算法

#include<iostream>
using namespace std;

//快速排序算法(从小到大)
//arr:需要排序的数组，begin:需要排序的区间左边界，end:需要排序的区间的右边界
void quickSort(int* arr, int begin, int end)
{
	//如果区间不只一个数
	if (begin < end)
	{
		int temp = arr[begin]; //将区间的第一个数作为基准数
		int i = begin; //从左到右进行查找时的“指针”，指示当前左位置
		int j = end; //从右到左进行查找时的“指针”，指示当前右位置
		//不重复遍历
		while (i < j)
		{
			//当右边的数大于基准数时，略过，继续向左查找
			//不满足条件时跳出循环，此时的j对应的元素是小于基准元素的
			while (i<j && arr[j] > temp)
				j--;
			//将右边小于等于基准元素的数填入右边相应位置
			arr[i] = arr[j];
			//当左边的数小于等于基准数时，略过，继续向右查找
			//(重复的基准元素集合到左区间)
			//不满足条件时跳出循环，此时的i对应的元素是大于等于基准元素的
			while (i < j && arr[i] <= temp)
				i++;
			//将左边大于基准元素的数填入左边相应位置
			arr[j] = arr[i];
		}
		//将基准元素填入相应位置
		arr[i] = temp;
		for (int i = 0; i < 8; i++)
			cout << arr[i] << " ";
		cout << endl;
		//此时的i即为基准元素的位置
		//对基准元素的左边子区间进行相似的快速排序
		quickSort(arr, begin, i - 1);
		//对基准元素的右边子区间进行相似的快速排序
		quickSort(arr, i + 1, end);
	}
	//如果区间只有一个数，则返回
	else
		return;
}
//利用快速排序的划分思想，编写算法将一组整数中所有奇数调到偶数之前。
void quickSort_(int arr[], int n)
{
	//如果区间不只一个数
	int i = 0;
	int j = n - 1;
	int temp;
	while(i < j)
	{
			while (i<j && arr[i] %2!=0)//找到偶数
				i++;
			while (i < j && arr[j]%2==0)//找到奇数
				j--;
			temp = arr[j];
			arr[j] = arr[i];
		//将基准元素填入相应位置
		arr[i] = temp;

	}
	//如果区间只有一个数，则返回
	printf("完成奇偶性排序后:");
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";
	cout << endl;

}

int main()
{
	int num[12] = { 23,45,17,11,13,89,72,26,3,17,11,13 };
	int n = 12;
	int num1[8] = { 438,241,567,704,256,852,123,205 };
	int n1 = 8;
	//quickSort(num1, 0, n1 - 1);
	quickSort_(num1, n1);
	quickSort_(num, n);
	/*
	cout << "排序后的数组为：" << endl;
	for (int i = 0; i < n; i++)
		cout << num[i] << ' ';
	cout << endl;
	*/

	return 0;
}